package demo;

import java.util.Arrays;

public class MyQuickSort {


    public static void main(String[] args) {
        int[] arr = {1,0,10,16,-1,5,-18};

        quickSort(arr,0,arr.length-1);
        //threeQuickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    private static void quickSort(int[] arr, int left, int right) {
        //递归出口
        if(left >= right){
            return;
        }
        //先进行分区
        int pivotIndex = partition(arr,left,right);

        //[left,pivotIndex - 1],[pivotIndex + 1 ,right] 递归调用
        quickSort(arr,left,pivotIndex-1);
        quickSort(arr,pivotIndex+1,right);
    }

    private static int partition(int[] arr, int left, int right) {
        //确定一个基准
        int pivot = arr[left];
        int i = left , j = right;

        while(i < j) {
            //在右边找到第一个比pivot小的数
            while (i < j && arr[j] >= pivot ) {
                j--;
            }
            //在左边找到第一个比pivot大的数
            while(i < j && arr[i] <= pivot) {
                i++;
            }
            //如果找到了
            if(i < j) {
                swap(arr,i,j);
            }
        }
        //最终将 i/j 和 left 交换
        swap(arr,i,left);
        return i;

    }

    private static void swap(int[] arr, int l , int r) {
        int temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }

    private static void threeQuickSort(int[] arr , int left , int right) {
        //递归出口
        if(left >= right){
            return;
        }
        //定义一个基准
        int pivot = arr[left];

        int lt = left ,gt = right  ;
        int i = left + 1;
        while (i <= gt) {
            //应该放右边
            if(arr[i] > pivot) {
                swap(arr,i,gt--);
            }else if(arr[i] < pivot) {
                swap(arr,i++,lt++);
            }else {
                i++;
            }
        }
        //[left,lt - 1] , [lt, gt] , [gt+1 , right]
        //继续递归
        threeQuickSort(arr,left,lt-1);
        threeQuickSort(arr,gt+1,right);
    }

}
